#include <cstdlib>
#include <iostream>
#include <vector>
#include "tp1.hpp"

using namespace std;
const int MAX=10100;

void grapherandom(int n, int m, int edge[][2]);

void composantes(int n, int m, int edge[][2], int comp[]);

void ecrituretailles(int n, int m, int comp[]);

int main(){
    	int n;     // Nombre de sommets.
    	int m;     // Nombre d'aretes.
    	cout << "Entrer le nombre de sommets:";
    	cin >>n;
    	cout << "Entrer le nombre d'aretes:";
    	cin >> m;
    	int edge[m][2];    // Tableau des aretes.
    	int comp[n];       // comp[i] est le numero de la composante contenant i.


	grapherandom(n,m,edge);

	for (int i=0; i<m; i++){
		cout<<edge[i][0]<<" , "<<edge[i][1]<<endl;
	}

	composantes(n,m,edge,comp);

	ecrituretailles(n,m,comp);

   	return 0;
}


void grapherandom(int n, int m, int edge[][2]){
	 int alea1=0, alea2=0;
	 srand(time(NULL));

	 for (int i=0; i<m; i++){
	 	alea1=rand()%n;
	 	alea2=rand()%n;
		edge[i][0]=alea1;
		edge[i][1]=alea2;
	 }
}


void composantes(int n, int m, int edge[][2], int comp[]){

	for (int i=0; i<n; i++){
		comp[i]=i;
	}

	cout<<endl<<"comp avant :"<<endl;

	for (int i=0; i<n; i++){
		cout<<comp[i]<<" ";
	}

	cout<<endl;

	int aux=0;
	for (int i=0; i<m; i++){
		if(comp[edge[i][0]]!=comp[edge[i][1]]){
			aux=comp[edge[i][0]];
			for (int j=0; j<n; j++){
				if (comp[j]==aux){
					comp[j]=comp[edge[i][1]];
				}
			}
		}
	}

	cout<<endl<<"comp apres :"<<endl;
	for (int i=0; i<n; i++){
		cout<<comp[i]<<" ";
	}
	cout<<endl;
}

void ecrituretailles(int n, int m, int comp[MAX]){

	int temp[MAX];
	int nbComp[MAX];


	for(int i(0); i<n; i++){

		temp[comp[i]]++;

	}

	for(int j(0); j<n; j++){

		if(temp[comp[j]]==1)
			nbComp[1]++;

		else if(temp[comp[j]]>1)
			nbComp[temp[j]]++;

	}


	cout<<"\nil y a "<<nbComp[1]<<" points isolés"<<endl;

	for(int k(2); k<n; k++){

		if(nbComp[k]>0)
			cout<<"il y a "<<nbComp[k]<<" composantes de taille "<<k<<endl;


	}

}


